import sun.invoke.empty.Empty;

public class BinarySearchTree {

    //节点结构
    static class TreeNode {
        public TreeNode left;//左子树
        public TreeNode right;//右子树
        public int val;//值

        public TreeNode(int val) {
            this.val = val;//构造方法为成员变量赋值
        }
    }

    //根节点
    public TreeNode root;

    //查找节点
    public TreeNode findNode(int val) {
        TreeNode node = root; //使node为根节点的一个代替
        if (node == null) { //根节点不为空
            return null;
        }
        while (node != null) { //根节点不为空
            if (node.val == val) {
                return node;//找到根节点就返回node
            }else if (node.val > val) {
                node = node.left;//根节点的值大于查找的值
            }else {
                node = node.right;//根节点的值小于查找的值
            }
        }
        return null;//没有该节点返回null
    }

    //插入节点
    public void insertNode(int val) {
        if (root == null) {
            root = new TreeNode(val);//新节点就是val值所在的节点
            return;//结束程序
        }
        TreeNode cur = root;//一个cur代替root根节点
        TreeNode parent = null;//根节点的上一个节点
        while(cur != null) {
            if (cur.val == val) {
                return;//如果这个节点存在直接结束程序
            }else if (cur.val > val) {
                parent = cur;
                cur = cur.left;//这个值小于根节点则往左子树走
            }else {
                parent = cur;
                cur = cur.right;//这个值大于根节点则往右子树走
            }
        }
        TreeNode node = new TreeNode(val);//使val值成为一个节点
        if (val > parent.val) {
            parent.right = node;//如果val值大于根节点值则把val值所在节点放在根节点右子树
        }else {
            parent.left = node;//否则放在左子树
        }
    }

    //删除节点
    public void delNode(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if (cur.val == key) {
                removeNode(cur,parent);
            }else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
                removeNode(cur,parent);
            }else {
                parent = cur;
                cur = cur.right;
                removeNode(cur,parent);
            }
        }
    }

    public void removeNode(TreeNode parent,TreeNode cur) {
        while (cur != null) {
            if (cur.left == null) {
                if (cur == root) {
                    root = cur.right;
                }else if(cur == parent.left) {
                    parent.left = cur.right;
                }else {
                    parent.right = cur.right;
                }
            }else if(cur.right == null) {
                if (cur == root) {
                    root = cur.left;
                }else if(cur == parent.left) {
                    parent.left = cur.left;
                }else {
                    parent.right = cur.left;
                }
            }else{
                TreeNode target = cur.right;
                TreeNode targetParent = cur;
                while (target.left != null) {
                    targetParent = target;
                    target = target.left;
                }
                cur.val = target.val;
                if (target == targetParent.left) {
                    targetParent.left = target.right;
                }else {
                    targetParent.right = target.right;
                }
            }

        }
    }
}
